package leet704binarysearch

func Search(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	for low <= high {
		// 此处直接计算中间值，使用 low+high 可能会导致溢出
		// mid := (low + high) / 2
		// 使用基址+偏移量的运算来计算中间值，避免溢出
		// mid := low + (high-low)/2
		// 如果偏移量使用位运算小路会更高
		mid := low + ((high - low) >> 1)
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			// 如果中间值小于目标值，则说明目标值在高位区，把低值挪到中间值下一个
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}
